package com.lyj.sc.paixu;

import java.util.Arrays;

/**
 * @Author: liyangjing
 * @Date: 2022/03/07/15:19
 * @Description:
 */
public class QuickSort{

    public static void main(String[] args) {
        int [] a ={36,25,78,35,96,45,20,11};
//        int[] ints = sortArray(a);
//        System.out.println(Arrays.toString(ints));
        quick2(a,0,a.length-1);
    }
    //单边循环
    public static void quick(int[] a,int l,int h){
        if(l>h){
            return;
        }
        sort2(a,l,h);
    }
    public static void sort2(int arr[], int low, int high) {
        if(low>high){
            return;
        }
        //找到基准点
        int pv = arr[high];
        //从低位开始比较
        int i = low;
        for(int j=i;j<high;j++){
            //若发现比基准点小 则交换。
            if(pv>arr[j]){
                swap(arr,i,j);
                i++;
            }
        }
        // 交换最低位i 和j
        swap(arr,i,high);
        System.out.println(Arrays.toString(arr));
        //分治算法
        sort2(arr,low,i-1);
        //分治
        sort2(arr,i+1,high);
    }



    //双边循环
    public static void quick2(int[] a,int l,int h){
        //相等就退出
        if(l>=h){
            return;
        }
        sort(a,l,h);
    }
    public static  void sort(int[] nums,int l,int h){
        //low 和high 相等就退出
        if(l>=h){
            return;
        }
        //基准点 左
        int pv = nums[l];
        int i=l;
        int j=h;
        while(i<j){
            //从右往左 找到比基准点小的
            while(i<j && nums[j]>pv){
                j--;
            }
            //从左往右 找到比基准点大的
            while(i<j && nums[i]<=pv){
                i++;
            }
            //交换
            swap(nums,i,j);
        }
        //假设排序好了的，只交换了一次swap（i，j），那么这里就要交换回来 swap(nums,l,j);
        swap(nums,l,j);
        System.out.println(Arrays.toString(nums));
        sort(nums,l,j-1);
        sort(nums,j+1,h);
    }

    //交换
    public static void swap(int []arr ,int i, int j){
        int temp;
        temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
}
